package xjggb.algorithm.树.二插搜索树;



import xjggb.algorithm.树.二插搜索树.printer.BinaryTreeInfo;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;

public class BinarySearchTree<E> implements BinaryTreeInfo {
    /*
    * 树的结点数量
    * */
    private int size;
    private Node<E> root;
    private Comparator<E> comparator;  //比较器
    public BinarySearchTree() {
    }
    /*
    * 添加比较器接口
    * */
    public BinarySearchTree(Comparator<E> comparable) {
        this.comparator=comparable;
    }

    public int size(){
        return 0;
    } // 元素的数量
    boolean isEmpty(){
        return false;
   } // 是否为空
    public void clear() {}// 清空所有元素
    public void add(E element){// 添加元素
        elementNotNullCheck(element);//element不能为null
//         第一次添加
        if (root==null){
            root=new Node<E>(element,null);
            size++;
            return;
        }
//        添加的不是第一个节点
//        找到父节点
        Node<E> parent = this.root;  //添加子节点的父节点
        Node<E> node = this.root; //定级父节点
        int cmp=0;   //定义存放的位置
        while (node!=null){
            cmp = compare(element, node.element);
             parent=node;  //记录当前父节点
            if(cmp>0){
                node = node.right;   //获取左子节点在赋值当做父节点
            }else if (cmp<0){
                node = node.left;  //获取右子节点在赋值当做父节点
            }else {
                //相等覆盖
                node.element=element;
                return;
            }
        }
//        插入到父节点的那个位置
        Node<E> newNode = new Node<E>(element, parent);
        if (cmp > 0){
            parent.right=newNode;
        }else {
            parent.left=newNode;
        }
        size++;

    }


    /*
    * 自定义遍历规则接口
    * */
    public  static  interface Visitor<E>{
        boolean visit(E element);
    }




    public void remove(E element){} // 删除元素
    public boolean contains(E element){
        return false;
    } // 是否包含某元素


    /*
    * 创建节点
    * */
    private static class Node<E> {
        E element;
        Node<E> left;
        Node<E> right;
        Node<E> parent;
        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }

        public boolean isLeaf() {
            return left == null && right == null;
        }

        public boolean hasTwoChildren() {
            return left != null && right != null;
        }
    }

    /*
    * 判断添加元素是否weinull
    * */
    private void elementNotNullCheck(E element) {
        if (element == null) {
            throw new IllegalArgumentException("element must not be null");
        }
    }

    /*
    * @return 返回值等于0，代表e1和e2相等；返回值大于0，代表e1大于e2；返回值小于于0，代表e1小于e2
    * */
    private int compare(E e1, E e2)
    {
      if (comparator!=null){
          return comparator.compare(e1,e2);
      }
        return ((Comparable<E>)e1).compareTo(e2);
    }

    public Object root() {
        return root;
    }

    public Object left(Object node) {
        return  ((Node<E>)node).left;
    }

    public Object right(Object node) {
        return  ((Node<E>)node).right;
    }

    public Object string(Object node) {
        Node<E> myNode = (Node<E>)node;
        String parentString = "null";
        if (myNode.parent != null) {
            parentString = myNode.parent.element.toString();
        }
       // return myNode.element + "_p(" + parentString + ")";
        return myNode.element;
    }


    /*
    * 前序遍历
    * */
    public void preorderTraversal(){
        preorderTraversal(root);
    }
    private void preorderTraversal(Node<E> node){
        if (node==null) return ;
        System.out.println("node.element = " + node.element);
        preorderTraversal(node.left);
        preorderTraversal(node.right);

    }


    /*
    * 中序遍历
    * */
    public void inorderTraversal(){
        inorderTraversal(root);
    }

    private void inorderTraversal(Node<E> node){
        /*
        * 从小到大
        * */
        if (node==null) return ;
        inorderTraversal(node.left);
        System.out.println("node.element = " + node.element);
        inorderTraversal(node.right);

        /*
        * 从大到小
        * */
//        inorderTraversal(node.right);
//        System.out.println("node.element = " + node.element);
//        inorderTraversal(node.left);

    }

    /*
    * 后续遍历
    * */

    public void postorderTraversal(){
        postorderTraversal(root);
    }
    private void postorderTraversal(Node<E> node){
        if (node==null) return ;
        postorderTraversal(node.left);
        postorderTraversal(node.right);
        System.out.println("node.element = " + node.element);
    }


    /*
    * 层序遍历
    * */
    public void levelOrderTranversal(){
        levelOrderTranversal(root);
    }
    private void levelOrderTranversal(Node<E> node){
        if (node==null)return; //        当节点为空直接退出
        Queue<Node<E>> queue = new LinkedList<Node<E>>();//        创建队列
        queue.offer(node);  //        入队
        while (!queue.isEmpty()){
            Node<E> poll = queue.poll(); //            获取数据
            System.out.println("poll.element = " + poll.element);
            /*
            * 判断节点左边是否有数据和判断右边是否有数据有都入队
            * */
            if (poll.left!=null){
                queue.offer(poll.left);
            }
            if (poll.right!=null){
                queue.offer(poll.right);
            }
        }
    }
    /*
    * 自定义规则遍历
    * */
    public void levelOrder(Visitor<E> visitor){
        //        当节点为空直接退出
        if (root==null||visitor==null)return;
//        创建队列
        Queue<Node<E>> queue = new LinkedList<Node<E>>();
//        入队
        queue.offer(root);
        while (!queue.isEmpty()){
//            获取数据
            Node<E> poll = queue.poll();
            /*
            * 把数据传出去  返回true退出循环
            * */
            if ( visitor.visit(poll.element))return;
            /*
             * 判断节点左边是否有数据和判断右边是否有数据有都入队
             * */
            if (poll.left!=null){
                queue.offer(poll.left);
            }

            if (poll.right!=null){
                queue.offer(poll.right);
            }
        }
    }

    /*
    * 树的高度
    * */

    public int height(){
        if (root==null) return 0;
        int height = 0;   //        树的高度
        int levelSize=1;  //        存储每一层元素
        Queue<Node<E>> queue = new LinkedList<Node<E>>();  //        创建队列
        queue.offer(root); //        入队
        while (!queue.isEmpty()){
            Node<E> poll = queue.poll();//            获取数据
            levelSize--;
            /*
             * 判断节点左边是否有数据和判断右边是否有数据有都入队
             * */
            if (poll.left!=null){
                queue.offer(poll.left);
            }
            if (poll.right!=null){
                queue.offer(poll.right);
            }
            if (levelSize==0){  //意味着即将进入下一层访问
                levelSize=queue.size();
                height++;
            }
        }
        return height;
    }

    /*
    * 反转二叉树
    * */
    public void reversalErgodic(){
       if (root==null)return;     //        当节点为空直接退出
//       创建创建队列
        Queue<Node<E>> queue = new LinkedList<>();
//        入队
        queue.offer(root);
        while (!queue.isEmpty()){
            Node<E> poll = queue.poll();  //出队获取数据
            System.out.println("poll.element = " + poll.element);
            /*
            * 判断左节点是否有数据和又子节点是否又数据
            * */
            Node<E> tmp = poll.left;
            poll.left=poll.right;
            poll.right=tmp;
            if (poll.left!=null){
                queue.offer(poll.left); //入队
            }
            if (poll.right!=null){
                queue.offer(poll.right); //入队
            }
        }
    }


    /*
    * 前驱节点
    * */
    private Node<E> predecessor(Node<E> node){

        if (node==null)return null;
//        前驱节点左子树当中（left.right.right.right....）
        Node<E> p = node.left;
        if (p!=null){
            while (p.right!=null){
                p=p.right;
            }
            return p;
        }
//        从父节点，祖父节点中寻找前驱节点
        while (node.parent!=null&& node== node.parent.left){
            node=node.parent;
        }
        /*
        * node.parent==null
        * 或者
        * node==node.parent.right
        * */
        return node.parent;
    }


    /*
    * 后驱节点
    * */

    private Node<E> successor(Node<E> node){
        if (node==null)return null;
//        后驱节点左子树当中（left.right.right.right....）
        Node<E> p = node.right;
        if (p!=null){
            while (p.left!=null){
                p=p.left;
            }
            return p;
        }
//        从父节点，祖父节点中寻找前驱节点
        while (node.parent!=null&& node== node.parent.right){
            node=node.parent;
        }
        /*
         * node.parent==null
         * 或者
         * node==node.parent.left
         * */
        return node.parent;
    }











}
